package experiment4.knapsack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Main {


    private static void generate(int[] w, int[] v) {
        Random random = new Random();
        for (int i = 0; i < w.length; i++) {
            w[i] = random.nextInt(w.length) + 1;
            v[i] = random.nextInt(w.length+10) + 1;
        }
    }

    public static void main(String[] args) {
        DynamicKnapsack dynamicKnapsack = new DynamicKnapsack();
        BacktrackKnapsack greedyKnapsack = new BacktrackKnapsack();
        BABMethodKnapsack babMethodKnapsack = new BABMethodKnapsack();
        Scanner scanner = new Scanner(System.in);
        int capacity = scanner.nextInt();//背包容量
        int n = scanner.nextInt();//商品数量
        int[] w = new int[n];
        int[] v = new int[n];

        ArrayList<Goods> goodsArrayList = new ArrayList<>();

        generate(w, v);

        for (int i = 0; i < n; i++) {
            goodsArrayList.add(new Goods(w[i], v[i]));
        }

        goodsArrayList.sort(new Goods());
        print(goodsArrayList);
        System.out.println("动态规划:");
        System.out.println(dynamicKnapsack.solution(goodsArrayList,capacity));
        System.out.println(Arrays.toString(dynamicKnapsack.solutionVector()));
        System.out.println("分支限界:");
        System.out.println(babMethodKnapsack.solution(goodsArrayList, capacity));
        System.out.println(Arrays.toString(babMethodKnapsack.solutionVector()));
        System.out.println("贪心算法:");
        System.out.println(greedyKnapsack.solution(goodsArrayList, capacity));
        System.out.println(Arrays.toString(greedyKnapsack.solutionVector()));


    }

    public static void print(ArrayList<Goods> goodsArrayList) {
        int[] w = new int[goodsArrayList.size()];
        int[] v = new int[goodsArrayList.size()];
        float[] p = new float[goodsArrayList.size()];
        for (int i = 0;i < goodsArrayList.size();i++){
            Goods goods = goodsArrayList.get(i);
            w[i] = goods.weight;
            v[i] = goods.value;
            p[i] = goods.weightValue;
        }
        System.out.println(Arrays.toString(w));
        System.out.println(Arrays.toString(v));
        System.out.println(Arrays.toString(p));

    }
}
